豆米的博客

阅读本文你需具备知识点：

二叉查找树(js版本的简单实现可以参考二叉查找树的简单学习)
准备纸和笔(自己动手画一画，这样方能真的理解)
推荐大家一个好用的在线生成红黑树的网站(这个不能演示过程)：Virtual
- 国内大家都推荐使用这个在线生成，不过打不开了，后来我找到原始网站，就把他贴在了自己的博客域名下，大家可以用一用：在线生成

1、libuv如何用红黑树？

libuv将红黑树的算法用在了signal上，我们先回顾一下signal是怎么使用的：

uv_signal_t signal_handle;
r = uv_signal_init(loop, &signal_handle);
CHECK(r, "uv_signal_init");

r = uv_signal_start(&signal_handle, signal_cb, SIGINT);

void signal_cb(uv_signal_t *handle, int signum) {
  printf("signal_cb: recvd CTRL+C shutting down\n");
  uv_stop(uv_default_loop()); //stops the event loop
}

当开发者每调用一次uv_signal_start的时候，都会往生成的红黑树中插入一个节点，当调用uv_signal_stop的时候，则会删除一个节点，如下：

static int uv__signal_start(uv_signal_t* handle,
                            uv_signal_cb signal_cb,
                            int signum,
                            int oneshot) {
  ... ...
  RB_INSERT(uv__signal_tree_s, &uv__signal_tree, handle);
  ... ...
}

static void uv__signal_stop(uv_signal_t* handle) {
  ... ...
  removed_handle = RB_REMOVE(uv__signal_tree_s, &uv__signal_tree, handle);
  ... ...
}

libuv使用宏的形式(源码在tree.h)，定义了一整套红黑树的完整实现，因为宏代码看起来比较费劲，我随意截了个图，大家可以瞄一眼：

本身红黑树就是很难搞懂的概念，加上C语言，所以太不友好了。于是我根据C语言的实现，改写成Js版本的，下面的讲解都是基于js语言的，所以大家勿慌~

2、红黑树的基本概念

2.1、为什么需要红黑树？

红黑树的基础是二叉搜索树，那么二叉搜索树不好吗？非要再整这么一个复杂的出来？二叉搜索树原本已经是个很好的数据结构，可以快速地找到一个给定关键字的数据项，并且可以快速地插入和删除数据项。但是二叉搜索树有个很麻烦的问题，如果树中插入的是随机数据，则执行效果很好，但如果插入的是有序或者逆序的数据，那么二叉搜索树的执行速度就变得很慢。因为当插入数值有序时，二叉树就是非平衡的了，排在一条线上，其实就变成了一个链表……它的快速查找、插入和删除指定数据项的能力就丧失了。比如下图的

为了能以较快的时间 O(logN) 来搜索一棵树，需要保证树总是平衡的（或者至少大部分是平衡的），这就是说对树中的每个节点在它左边的后代数目和在它右边的后代数目应该大致相等。红-黑树的就是这样的一棵平衡树，对一个要插入的数据项，插入过程中要检查会不会破坏树的特征，如果破坏了，程序就会进行纠正，根据需要改变树的结构，从而保持树的平衡。

Tips: 有的童鞋可能会提出问题：AVL和红黑树之间，为啥红黑树用的场景更多？其实这是一个性能平衡的问题，固然AVL的节点查找比红黑树好，但是因为其严苛的条件，导致在每次插入和删除的时候需要做的运算比红黑树多。所以牺牲一点查找时间，保证每次插入和删除节点的时候性能也不会太差。

2.2、红黑树特征

性质1：每个节点要么是黑色，要么是红色。
性质2：根节点是黑色。
性质3：每个叶子节点（NIL）是黑色。
性质4：每个红色结点的两个子结点一定都是黑色。
性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

然后根据以上特征有如下推论：

推论1：红黑树中不会出现两个红色结点相邻的情形
推论2：树中最短的可能出现的路径是都是黑色结点的路径
推论3：树中最长的可能出现的路径是红色结点和黑色结点交替的路径
推论4：每条路径上均包含相同数目的黑色结点，所以红黑树确保没有一条路径会比其他路径长出2倍
推论5：如果一个结点存在黑子结点，那么该结点肯定有两个子结点

由此我们得到节点的数据结构：

function Node(data) {
  this.leftNode = null
  this.rightNode = null
  this.parentNode = null
  this.data = data
  this.rbColor = RED // 初始化为红色的原因下面有说到
}

2.3、红黑树的修正操作

红黑树的修正都是基于旋转和变色的，因为我们在搞懂插入一个节点之后会怎么修正之前，我们需要读懂左旋和右旋。

2.3.1、左旋

下图是一个左旋的动画：

从图中可以看出，所谓左旋就是将要旋转的节点往左边挪动，也就是逆时针走向，完成的操作有以下三件事：

将S的左子节点赋给E的右子节点,并将E赋给S左子节点的父节点(E左子节点非空时)
将E的父节点p(非空时)赋给E的父节点，同时更新E之前的父节点的子节点为y(可能是左或右，取决于当时E节点的位置)
将S的左子节点设为E，将E的父节点设为S

根据上面的介绍，用Js实现的代码如下(代码中的注释以函数的顶部注释为准)：

/*************对红黑树节点x进行左旋操作 ******************/
/*
 * 左旋示意图：对节点x进行左旋
 *     p                       p
 *    /                       /
 *   x                       y
 *  / \                     / \
 * lx  y      ----->       x  ry
 *    / \                 / \
 *   ly ry               lx ly
 * 左旋做了三件事：
 * 1. 将y的左子节点赋给x的右子节点,并将x赋给y左子节点的父节点(y左子节点非空时)
 * 2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)
 * 3. 将y的左子节点设为x，将x的父节点设为y
 ********************************************************/
rotateLeft(beRotatedNode) {
  // x节点的右节点y
  const rightNode = beRotatedNode.rightNode
  // x节点的右节点变更掉，将y的左节点赋值过来
  beRotatedNode.rightNode = rightNode.leftNode
  // 如果y节点的左节点有值，那么x将是y节点的左节点的父节点
  if (rightNode.leftNode) {
    rightNode.leftNode.parentNode = beRotatedNode
  }
  // 将x的父节点赋值给y节点的父节点
  rightNode.parentNode = beRotatedNode.parentNode
  // 如果x的父节点存在的话
  if (beRotatedNode.parentNode) {
    // 如果x节点之前是其父节点的左节点
    if (beRotatedNode === beRotatedNode.parentNode.leftNode) {
      beRotatedNode.parentNode.leftNode = rightNode
    } else {
      beRotatedNode.parentNode.rightNode = rightNode
    }
  } else {
    // 如果x的父节点为空，那么说明是根节点
    this.root = rightNode
  }

  // 3. 将y的左节点设为x，将x的父节点设为y
  rightNode.leftNode = beRotatedNode
  beRotatedNode.parentNode = rightNode
}

2.3.2、右旋

右旋的操作与左旋相反，还是有动画：

具体的就不再赘述，实现的代码如下：

/*************对红黑树节点y进行右旋操作 ******************/
/*
* 右旋示意图：对节点y进行右旋
*        p                   p
*       /                   /
*      y                   x
*     / \                 / \
*    x  ry   ----->      lx  y
*   / \                     / \
* lx  rx                   rx ry
* 右旋做了三件事：
* 1. 将x的右子节点赋给y的左子节点,并将y赋给x右子节点的父节点(x右子节点非空时)
* 2. 将y的父节点p(非空时)赋给x的父节点，同时更新p的子节点为x(左或右)
* 3. 将x的右子节点设为y，将y的父节点设为x
*/
rotateRight(beRotatedNode) {
  // y节点的左节点x
  const leftNode = beRotatedNode.leftNode
  // y节点的左节点变更掉，将x的右节点赋值过来
  beRotatedNode.leftNode = leftNode.rightNode
  // 如果x节点的右节点有值，那么y将是x节点的右节点的父节点
  if (leftNode.rightNode) {
    leftNode.rightNode.parentNode = beRotatedNode
  }
  // 将y的父节点赋值给x节点的父节点
  leftNode.parentNode = beRotatedNode.parentNode
  // 如果y的父节点存在的话
  if (beRotatedNode.parentNode) {
    // 如果y节点之前是其父节点的左节点
    if (beRotatedNode === beRotatedNode.parentNode.leftNode) {
      beRotatedNode.parentNode.leftNode = leftNode
    } else {
      beRotatedNode.parentNode.rightNode = leftNode
    }
  } else {
    // 如果x的父节点为空，那么说明是根节点
    this.root = leftNode
  }

  // 3. 将x的左节点设为y，将y的父节点设为x
  leftNode.rightNode = beRotatedNode
  beRotatedNode.parentNode = leftNode
}

3、红黑树的插入

接着我们进入正题，了解插入之前，我们先约定好一些术语，这样结合代码阅读的时候不至于懵。如下图：

所有节点的一些称呼都标注清楚了，后面的插入和删除的操作都是基于这些称呼的。

首先以二叉搜索树的方式插入结点，并将其着为红色。如果着为黑色，则会违背性质5，不便调整；如果着为红色，可能会违背性质2或性质4，可以通过相对简单的操作，使其恢复红黑树的性质。

将一个节点插入到红黑树中，需要执行哪些步骤呢？首先，实例化一个新节点，然后将红黑树当作一颗二叉查找树，查找适合的位置将节点插入；最后，通过"旋转和重新着色"等一系列操作来修正该树，使之重新成为一颗红黑树。

详细描述如下：

3.1、第一步

实例化新节点，代码如下：const node = new Node(data)

3.2、第二步

将红黑树当作一颗二叉查找树，查找适合节点插入的位置。这一步查找的逻辑其实很简单，总结如下：

根据节点的值，从根节点开始遍历，找到适合插入的父节点
将该插入的节点和父节点建立联系

实现代码如下：

__insert(node) {
  let root = this.root
  let parent = null
  let compareRes
  // 2. 查找插入节点适合存放的位置，并与其父节点建立联系
  while(root !== null) {
    parent = root

    compareRes = node.data - root.data
    // 如果插入的节点比当前父节点大，那么继续寻找该父节点的右节点
    if (compareRes > 0) {
      root = root.rightNode
    } else if (compareRes < 0) {
      root = root.leftNode
    } else {
      return root
    }
  }
  // 找到插入节点的父节点了，此时parent表示的就是插入节点的父节点
  node.parentNode = parent

  // 接着判断是插入到该父节点的左边还是右边
  if (parent) {
    if (compareRes < 0) {
      parent.leftNode = node
    } else {
      parent.rightNode = node
    }
  } else {
    this.root = node
  }
  // 3. 修整整个红黑树
  this.__insert_color(this.root, node)
  return null
}

3.3、第三步

通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。

如果是第一次插入，由于原树为空，所以只会违反红黑树的特征2，所以只要把根节点涂黑即可；如果插入节点的父节点是黑色的，那不会违背红黑树的特征，什么也不需要做；

但是遇到如下三种情况时(以下统一称为场景3)，我们就要开始变色和旋转了：

插入节点的父节点和其叔叔节点均为红色的；
插入节点的父节点是红色，叔叔节点是黑色，且插入节点是其父节点的右子节点；
插入节点的父节点是红色，叔叔节点是黑色，且插入节点是其父节点的左子节点。

该场景下有这么一个推论，需要记住：如果插入的父结点为红结点，那么该父结点不可能为根结点，所以插入结点总是存在祖父结点。

场景3.1、叔叔结点存在并且为红结点

从红黑树性质4可以，祖父结点肯定为黑结点，因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是：黑红红。显然最简单的处理方式是把其改为：红黑红。

因此处理方式是：

将父节点和叔叔节点设置为黑色
将祖父节点设置为红色
把祖父设置为当前插入结点，继续调整红黑树

场景3.2、叔叔结点不存在或为黑结点，并且插入结点的父结点是祖父结点的左子结点

单纯从插入前来看，叔叔结点非红即为叶子结点(Nil)。因为如果叔叔结点为黑结点，而父结点为红结点，那么叔叔结点所在的子树的黑色结点就比父结点所在子树的多了，这不满足红黑树的性质5。后续情景同样如此，不再多做说明了。

前文说了，需要旋转操作时，肯定一边子树的结点多了或少了，需要租或借给另一边。插入显然是多的情况，那么把多的结点租给另一边子树就可以了。

场景3.2.1、插入结点是其父结点的左子结点

左边两个红结点，右边不存在，那么一边一个刚刚好，并且因为为红色，肯定不会破坏树的平衡。因此处理方式是：

将父节点设为黑色
将祖父节点设为红色
对祖父节点进行右旋

场景3.2.2、插入结点是其父结点的右子结点

这种情景显然可以通过旋转将问题归一化到3.2.1小节的情况，因此处理方式如下：

对父节点进行左旋
把父节点设置为插入结点，归一化到3.2.1小节的情况后继续处理

场景3.3、叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的右子结点

该情景对应情景3.2，只是方向反转，不做过多说明了，直接给出结论。

场景3.3.1、插入结点是其父结点的右子结点

处理方式：

将父节点设为黑色
将祖父节点设为红色
对祖父节点进行左旋

场景3.3.2、插入结点是其父结点的右子结点

处理方式：

对父节点进行右旋
把父节点设置为插入结点，归一化到3.3.1小节的情况后继续处理

综上所述，实现的代码如下，代码有注释，一一对应上面的所有情况：

__insert_color(root, node) {
  let parent = node.parentNode
  let gparent, uncle

  // 第一种情况和第二种情况都不会进入这个while语句，所以都是很简单的
  // 只有第三种情况才会进入，也就是父节点存在并且父节点是红色
  while(parent !== null && parent.rbColor === RED) {
    gparent = parent.parentNode
    // 如果父节点是祖父节点的左节点
    if (parent === gparent.leftNode) {
      // 取叔叔节点，也就是父节点的兄弟节点
      uncle = gparent.rightNode
      // case3.1情况：如果叔叔节点存在并且颜色是红色
      if (uncle && uncle.rbColor === RED) {
        // 1、将叔叔节点、父节点、祖父节点分别置为黑黑红
        uncle.rbColor = BLACK
        parent.rbColor = BLACK
        gparent.rbColor = RED
        // 2、将祖父节点置为当前节点
        node = gparent
        // 祖父节点变更后，父节点必然也得变更
        parent = node.parentNode
        continue
      }
      // case3.2.2、如果叔叔节点不存在或者叔叔节点是黑色，并且插入的节点是在父节点的右边
      // 因为该情况最后会归一化到case3.2.1的情况，所以需要先执行
      if (parent.rightNode === node) {
        // 1、以父节点为支点，进行左旋
        this.rotateLeft(parent)
        // 旋转之后需要重新设置
        uncle = parent
        parent = node
        node = uncle
      }
      // 上面一种情况最后要归一化到最后的这种情况case3.2.1：叔叔节点不存在或者叔叔节点是黑色的，并且插入
      // 的节点是在父节点的左边
      // 1、将父节点和祖父节点分别设置为黑红
      parent.rbColor = BLACK
      gparent.rbColor = RED
      // 2、对祖父节点进行右旋
      this.rotateRight(gparent)
      // 更新父节点
      parent = node.parentNode
    } else {
      // 父节点是祖父节点的右节点，情况和上面完全相反

      // 取叔叔节点，也就是父节点的兄弟节点
      uncle = gparent.leftNode
      // case3.1情况：如果叔叔节点存在并且颜色是红色
      if (uncle && uncle.rbColor === RED) {
        // 1、将叔叔节点、父节点、祖父节点分别置为黑黑红
        uncle.rbColor = BLACK
        parent.rbColor = BLACK
        gparent.rbColor = RED
        // 2、将祖父节点置为当前节点
        node = gparent
        // 祖父节点变更后，父节点必然也得变更
        parent = node.parentNode
        continue
      }
      // case3.3.2、如果叔叔节点不存在或者叔叔节点是黑色，并且插入的节点是在父节点的右边
      // 因为该情况最后会归一化到case3.3.1的情况，所以需要先执行
      if (parent.leftNode === node) {
        // 1、以父节点为支点，进行右旋
        this.rotateRight(parent)
        // 旋转之后需要重新设置
        uncle = parent
        parent = node
        node = uncle
      }
      // 上面一种情况最后要归一化到最后的这种情况case3.3.1：叔叔节点不存在或者叔叔节点是黑色的，并且插入
      // 的节点是在父节点的右边
      // 1、将父节点和祖父节点分别设置为黑红
      parent.rbColor = BLACK
      gparent.rbColor = RED
      // 2、对祖父节点进行左旋
      this.rotateLeft(gparent)
      // 更新父节点
      parent = node.parentNode
    }
  }
  this.root.rbColor = BLACK
}

4、红黑树的删除

将红黑树内的某一个节点删除。需要执行的操作依次是：首先，将红黑树当作一颗二叉查找树，将该节点从二叉查找树中删除；然后，通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。详细描述如下：

第一步：将红黑树当作一颗二叉查找树，将节点删除。这和"删除常规二叉查找树中删除节点的方法是一样的"。分3种情况：

① 被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。

② 被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。

③ 被删除节点有两个儿子。那么，先找出它的后继节点(也就是大于被删除结点的最小结点)；在这里，后继节点相当于替身，在将后继节点的内容复制给"被删除节点"之后，再将后继节点删除。这样就巧妙的将问题转换为"删除后继节点"的情况了，下面就考虑后继节点。在"被删除节点"有两个非空子节点的情况下，它的后继节点不可能是双子非空。既然"的后继节点"不可能双子都非空，就意味着"该节点的后继节点"要么没有儿子，要么只有一个儿子。若没有儿子，则按"情况① "进行处理；若只有一个儿子，则按"情况② "进行处理。

这么一说，于是我们有了如下推论：删除操作删除的结点可以看作删除替代结点，而替代结点最后总是在树末

示意图如下：

第二步：通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。

因为"第一步"中删除节点之后，可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来修正该树，使之重新成为一棵红黑树。

4.1、第一步

根据以上罗列的情况，处理三种情况。实现代码如下：

__remove(node) {
  let replaceNode = node
  // 如果被删除的节点左右节点都不为空
  if (node.leftNode && node.rightNode) {
    // 先找出被删除节点的后继节点（大于删除结点的最小结点）来当做替换节点
    let replaceNode = node.rightNode
    while(replaceNode.leftNode) {
      replaceNode = replaceNode.leftNode
    }

    node.data = replaceNode.data
  }
  const parent = replaceNode.parentNode
  const color = replaceNode.rbColor
  // 这里有着足够的隐含信息，如果被删除节点不是左右节点都有，那么这里的child是null或者左右节点之一，
  // 如果被删除节点左右节点皆有，那么这里的是替换节点，而替换节点的左节点肯定是不存在的，只能是右节点或者null
  const child = replaceNode.rightNode || replaceNode.leftNode
  if (child) {
    child.parentNode = parent
  }
  if (parent) {
    if (parent.leftNode === replaceNode) {
      parent.leftNode = child
    } else {
      parent.rightNode = child
    }
  } else {
    this.root = child
  }
  if (color === BLACK) {
    this.__remove_color(child, parent)
  }
  replaceNode = null
}

如果刚好删除的节点是黑色，那么开始我们的红黑树重建

4.2、第二步

红黑树的重建，这个时候只有替换的节点是黑色的时候，才需要重建，因此忽略场景1(替换结点是红色结点)，直接说场景2：

场景2.1、替换结点是其父结点的左子结点

场景2.1.1、替换结点的兄弟结点是红结点

处理方式：

将兄弟设为黑色将父节点设为红色对父节点进行左旋，归一化到场景2.1.2.3

场景2.1.2、替换结点的兄弟结点是黑结点

该场景又根据兄弟节点的子节点的不同，分为不同的场景

场景2.1.2.1、替换结点的兄弟结点的右子结点是红结点，左子结点任意颜色

将兄弟节点的颜色设为父节点的颜色将父节点设为黑色将兄弟节点的右节点设为黑色对父节点进行左旋

场景2.1.2.2、替换结点的兄弟结点的右子结点为黑结点，左子结点为红结点

将兄弟节点设为红色将兄弟节点的左节点设为黑色对兄弟节点进行右旋，归一化到场景2.1.2.1进行处理

场景2.1.2.3、替换结点的兄弟结点的子结点都为黑结点

将兄弟节点设为红色把父节点作为新的替换结点重新进行删除结点情景处理

场景2.2、替换结点是其父结点的右子结点

场景2.2.1、替换结点的兄弟结点是红结点

将兄弟节点设为黑色将父节点设为红色对父节点进行右旋，归一化到场景2.2.2.3

场景2.2.2、替换结点的兄弟结点是黑结点

场景2.2.2.1、替换结点的兄弟结点的左子结点是红结点，右子结点任意颜色

将兄弟节点的颜色设为父节点的颜色将父节点设为黑色将兄弟节点的左节点设为黑色对父节点进行右旋

场景2.2.2.2、替换结点的兄弟结点的左子结点为黑结点，右子结点为红结点

将兄弟设为红色将兄弟节点的右节点设为黑色对兄弟节点进行左旋，归一化到场景2.2.2.1

场景2.2.2.3、替换结点的兄弟结点的子结点都为黑结点

将兄弟节点设为红色把父节点作为新的替换结点重新进行删除结点情景处理

完整实现代码如下：

// node表示待修正的节点，即后继节点的子节点（因为后继节点被删除了）
__remove_color(node, parent) {
  let brother
  while((node === null || node.rbColor === BLACK) && node !== this.root) {
    // 场景2.1、替换结点是其父结点的左子结点
    if (node == parent.leftNode) {
      brother = parent.rightNode // 取兄弟节点
      // 场景2.1.1、替换结点的兄弟结点是红结点
      if (brother.rbColor === RED) {
        brother.rbColor = BLACK
        parent.rbColor = RED
        this.rotateLeft(parent)
        // 归一化到场景2.1.2.3
        brother = parent.rightNode
      }
      // 场景2.1.2、替换结点的兄弟结点是黑结点
      // 场景2.1.2.3、替换结点的兄弟结点的子结点都为黑结点
      if ((brother.leftNode === null || brother.leftNode.rbColor === BLACK) && (brother.rightNode === null || brother.rightNode.rbColor === BLACK)) {
        brother.rbColor = RED
        node = parent
        parent = node.parentNode
      } else {
        // 场景2.1.2.2、替换结点的兄弟结点的右子结点为黑结点，左子结点为红结点
        if (brother.rightNode === null || brother.rightNode.rbColor === BLACK) {
          if (brother.leftNode) {
            brother.leftNode.rbColor = BLACK
          }
          brother.rbColor = RED
          // 右旋后归一化到场景2.1.2.1
          this.rotateRight(brother)
          brother = parent.rightNode
        }
        // 场景2.1.2.1、替换结点的兄弟结点的右子结点是红结点，左子结点任意颜色
        brother.rbColor = parent.rbColor
        parent.rbColor = BLACK
        if (brother.rightNode) {
          brother.rightNode.rbColor = BLACK
        }
        this.rotateLeft(parent)
        node = this.root
        break
      }
    } else {
      // 场景2.2、替换结点是其父结点的右子结点
      brother = parent.leftNode
      // 场景2.2.1、替换结点的兄弟结点是红结点
      if (brother.rbColor === RED) {
        brother.rbColor = BLACK
        parent.rbColor = RED
        // 右旋后会进入场景2.2.2.3
        this.rotateRight(parent)
        brother = parent.leftNode
      }

      // 场景2.2.2、替换结点的兄弟结点是黑结点
      // 场景2.2.2.3、替换结点的兄弟结点的子结点都为黑结点
      if ((brother.leftNode === null || brother.leftNode.rbColor === BLACK) && (brother.rightNode === null || brother.rightNode.rbColor === BLACK)) {
        brother.rbColor = RED
        node = parent
        parent = node.parentNode
      } else {
        // 场景2.2.2.2、替换结点的兄弟结点的左子结点为黑结点，右子结点为红结点
        if (brother.leftNode === null || brother.leftNode.rbColor === BLACK) {
          if (brother.rightNode) {
            brother.rightNode.rbColor = BLACK
          }
          brother.rbColor = RED
          // 左旋后归一化到场景2.2.2.1
          this.rotateLeft(brother)
          brother = parent.leftNode
        }

        // 场景2.2.2.1、替换结点的兄弟结点的左子结点是红结点，右子结点任意颜色
        brother.rbColor = parent.rbColor
        parent.rbColor = BLACK

        if (brother.leftNode) {
          brother.leftNode.rbColor = BLACK
        }
        this.rotateRight(parent)
        node = this.root
        break
      }
    }
  }
  if (node) {
    node.rbColor = BLACK
  }
}

从libuv源码中学习红黑树

1、libuv如何用红黑树？

2、红黑树的基本概念

2.1、为什么需要红黑树？

2.2、红黑树特征

2.3、红黑树的修正操作

2.3.1、左旋

2.3.2、右旋

3、红黑树的插入

3.1、第一步

3.2、第二步

3.3、第三步

场景3.1、叔叔结点存在并且为红结点

场景3.2、叔叔结点不存在或为黑结点，并且插入结点的父结点是祖父结点的左子结点

场景3.2.1、插入结点是其父结点的左子结点

场景3.2.2、插入结点是其父结点的右子结点

场景3.3、叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的右子结点

场景3.3.1、插入结点是其父结点的右子结点

场景3.3.2、插入结点是其父结点的右子结点

4、红黑树的删除

4.1、第一步

4.2、第二步

场景2.1、替换结点是其父结点的左子结点

场景2.1.1、替换结点的兄弟结点是红结点

场景2.1.2、替换结点的兄弟结点是黑结点

场景2.1.2.1、替换结点的兄弟结点的右子结点是红结点，左子结点任意颜色

场景2.1.2.2、替换结点的兄弟结点的右子结点为黑结点，左子结点为红结点

场景2.1.2.3、替换结点的兄弟结点的子结点都为黑结点

场景2.2、替换结点是其父结点的右子结点

场景2.2.1、替换结点的兄弟结点是红结点

场景2.2.2、替换结点的兄弟结点是黑结点

场景2.2.2.1、替换结点的兄弟结点的左子结点是红结点，右子结点任意颜色

场景2.2.2.2、替换结点的兄弟结点的左子结点为黑结点，右子结点为红结点

场景2.2.2.3、替换结点的兄弟结点的子结点都为黑结点

参考

公众号关注一波~

关于评论和留言